package UnionFind;

public class _839_SimilarStringGroups {
    String[] A;
    public int numSimilarGroups(String[] A) {
        this.A = A;
        int groups = 0;
        for (int i = 0; i < A.length; i++) {
            if(A[i]==null) continue;
            String s = A[i];
            A[i] = null;
            dfs(s);
            groups++;
        }
        return groups;
    }


    public void dfs(String s) {
        for (int i = 0; i < A.length; i++) {
            if(A[i]==null) continue;
            if (comp(s, A[i])) {
                String ts = A[i];
                A[i] = null;
                dfs(ts);
            }
        }
    }

    public boolean comp(String s1, String s2) {
        int diff = 0;
        int[] alpha = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            alpha[s1.charAt(i) - 'a']++;
            if (s1.charAt(i) != s2.charAt(i)) {
                diff++;
            }
            if (diff > 2) {
                break;
            }
        }
        boolean dupli = false;
        for (int i = 0; i < alpha.length; i++) {
            if (alpha[i] > 1) {
                dupli = true;
                break;
            }
        }
        return diff == 2 || (diff==0 && dupli);
    }
}
